import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

public class RegexToNFA {
    List<Character> transchar = new ArrayList<>();
    Stack<NFAGraph> stack = new Stack<NFAGraph>();
    char c;
    NFAGraph temp, left, right;

    RegularUtil u = new RegularUtil();

    /**
     * 判断字符在transchar中是否重复
     * @param c
     * @return
     */
    public boolean isDuplicate(char c) {
        boolean test = true;
        for (int j = 0; j < transchar.size(); j++) {
            if(c == transchar.get(j)){
                test = false;
            }
        }
        if (c != '#' && test) {
            transchar.add(c);
        }
        return test;
    }

    /**
     * 正规式转NFA
     * @param postfix
     * @return
     */
    public NFAGraph regex_NFA(String postfix){

        for(int i = 0; i < postfix.length(); i++){

            c = postfix.charAt(i);
            if(c == '+'){
                //栈顶为右操作数
                right = stack.pop();
                //次栈顶为右操作数
                left = stack.pop();
                temp = u.join_Graph(left, right);
                stack.push(temp);
            }else if(c == '*'){
                //*匹配左边的操作数，取栈顶为左边操作数
                left = stack.pop();
                temp = u.star_Graph(left);
                stack.push(temp);
            }
            else if(c == '|'){
                //left|right
                right = stack.pop();
                left = stack.pop();
                temp = u.union_Graph(left, right);
                stack.push(temp);
            }else{
                temp =  u.initState(c);
                stack.push(temp);
                //判断操作数是否重复，不重复则加入transchar
                isDuplicate(c);
            }
        }
        //栈顶为最终生成的NFA
        temp = stack.pop();
        //字符集为tranchar
        temp.access = transchar;
        return temp;
    }

    /**
     * 正规式转NFA方法封装，由整个程序调用
     * @return
     */
    public static NFAGraph regex_NFA_method(){
        RegularUtil regularUtil = new RegularUtil();
        RegexToNFA nfa = new RegexToNFA();
        Scanner in = new Scanner(System.in);
        System.out.println("please input a regex");
        String regex =in.next();
        if (regularUtil.isMatchParenthesis(regex) && regularUtil.isCharacter(regex)) {
            //添加’+’符号
            if(regex.length()<2){
                regex = regex;
            }else {
                regex = regularUtil.joinAddSymbol(regex);
                System.out.println("加入+号的正则表达式:" + regex);
            }
            //中缀表达式转后缀表达式
            regex = regularUtil.infix_Suffix(regex);
            System.out.println("后缀表达式:" + regex);
            //转后缀表达式为NFA
            NFAGraph nfaGraph = nfa.regex_NFA(regex);
            //打印NFA
            System.out.println("------------------------------------以下是正规式转化NFA--------------------------------------");
            Global.printGraph(nfaGraph);

            return nfaGraph;
        }else{
            System.out.println("输入的正则表达式不合法");
            return null;
        }
    }

    /**
     * 正规式转NFA单独测试
     * @param args
     */
    public static void main(String[] args) {
        regex_NFA_method();
    }
}
